package com.litchishell.easy;

import java.util.*;

/**
 * @author LitchiShell
 * @description: 题目20：有效的括号
 * @create 2022-08-19
 */
public class Solution005 {

    // 常规解法
    public static boolean isValid(String s) {
        if (s == null || s.length() % 2 != 0) {
            return false;
        }
        Map<String, String> map = new HashMap<>();
        map.put("(", ")");
        map.put("[", "]");
        map.put("{", "}");
        Stack<String> stock = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            String str1 = s.substring(i, i + 1);
            if (!stock.empty()) {
                // 查看栈顶元素并返回栈顶元素
                String peek = stock.peek();
                if (str1.equals(map.get(peek))) {
                    // 移除栈顶元素
                    stock.pop();
                    continue;
                }
            }
            // 添加元素
            stock.push(str1);
        }
        return stock.empty();
    }

    // 官网解法
    public boolean isValidCopy(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String s = "{}";
        System.out.println(isValid(s));
    }
}
